package 滑动窗口;

import common.GeneralFunction;

public class No3无重复字符的最长子串 {

    /**
     * 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
     * 示例 1:
     * 输入: "abcabcbb"
     * 输出: 3
     * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
     */

    public int lengthOfLongestSubstring(String s) {

        int[] freq=new int[256];//index存放ascii码,值为一个字符的个数
        int result=0;
        int left=0;
        int right=0;

        while(left<s.length()){

            //1.数组的ascii码对应的下标里的值是否为0
            //2.为0就让右指针++(下标是否溢出),再让数组对应的++
            //3.不为0就让左指针--,再让数组对应的--
            //4.最后看max即可,因为只取最长的,所以--的中间态对max无影响

            /**
             * 得知一个做题要素,把一个变量的作用域尽量压缩,越小越好
             */

            if(right<s.length()&&freq[s.charAt(right)]==0){
                //新加的为0,右指针往右移动
                char cr=s.charAt(right);
                freq[cr]++;//value++
                right++;//去添加下一个
            }else{
                //新加的已经存在,左指针往右移动
                char cl=s.charAt(left);
                freq[cl]--;//value--
                left++;//去掉目标
            }

            result=Math.max(right-left,result);

        }


        return result;
    }

    public int lengthOfLongestSubstring2(String s){

        int left=0;
        int right=0;
        int[] frep=new int[256];
        int max=0;

        //此题非窗口题

        while (right<s.length()){

            char c1=s.charAt(right);
            char c2=s.charAt(left);
            if(frep[c1]>0){
                //左指针移动
                frep[c2]--;
                left++;
            }else{
                //右指针移动
                frep[c1]++;
                right++;
            }

            max=Math.max(max,right-left);
        }

        return max;
    }

    public static void main(String[] args) {
        GeneralFunction generalFunction=new GeneralFunction(No3无重复字符的最长子串.class,"pwwkew");
        generalFunction.runAllMethod();
    }

}
